import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length == 0 || (lists.length == 1 && lists[0] == null)) return null;
        ListNode head = new ListNode();
        Queue<ListNode> queue = new PriorityQueue<>((ListNode o1, ListNode o2) -> o1.val - o2.val);
        int len = lists.length;
        ListNode newCur = head;
        //把所有链表的头节点都放进堆中
        for(int i = 0; i < len; i++){
            if(lists[i] != null){
                queue.offer(lists[i]);
            }
        }
        while(!queue.isEmpty()){
            ListNode node = queue.poll();
            newCur.next = node;
            if(node.next != null){
                queue.offer(node.next);
            }
            newCur = newCur.next;
        }
        return head.next;
    }
}